#include <vector>
using std::vector;
class Solution
{
public:
    static vector<int>& sortArray(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    static constexpr int INSERTSORT_SIZE = 10;

    static int partion(vector<int>& nums, int s, int e)
    {
        int m = s + (e - s) / 2;
        if (m != s) {
            if (nums[s] > nums[e]) {
                swap(nums[s], nums[e]);
            }
            if (nums[m] > nums[e]) {
                swap(nums[m], nums[e]);
            }
            if (nums[m] > nums[s]) {
                swap(nums[m], nums[s]);
            }
        }
        int pivot = nums[s];
        while (s < e) {
            while (s < e && nums[e] >= pivot)
                --e;
            if (s < e)
                nums[s] = nums[e];
            while (s < e && nums[s] <= pivot)
                ++s;
            if (s < e)
                nums[e] = nums[s];
        }
        nums[s] = pivot;
        return s;
    }
    static void quickSort(vector<int>& nums, int s, int e)
    {
        if (s < e) {
            if (e - s < INSERTSORT_SIZE) {
                insertSort(nums, s, e);
            }
            else {
                int idx = partion(nums, s, e);
                quickSort(nums, s, idx - 1);
                quickSort(nums, idx + 1, e);
            }
        }
    }
    static void insertSort(vector<int>& nums, int s, int e)
    {
        if (s < e) {
            for (int i = 1; i <= e; ++i) {
                int cur = nums[i];
                int j   = i - 1;
                for (; i >= s && nums[j] > cur; --j) {
                    nums[j + 1] = nums[j];
                }
                nums[j + 1] = cur;
            }
        }
    }
    static void swap(int& a, int& b)
    {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
};

vector<int>& SortArray(vector<int>& nums)
{
    return Solution::sortArray(nums);
}